package middle;

import java.util.*;

/**
 * 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

 * 叶子节点 是指没有子节点的节点。
 * 链接：https://leetcode-cn.com/problems/path-sum-ii
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class PathSumII {
    /**
     * dfs先序遍历
     * */
    class Solution {
        List<List<Integer>> result = new ArrayList<>();
        public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
            if(Objects.isNull(root)){
                return Collections.emptyList();
            }
            dfs(root, targetSum, new ArrayList<Integer>(), 0);
            return result;
        }
        /**
         * 一个先序遍历的过程
         * 基线条件
         * 如果当前结点为null
         * */
        private void dfs(TreeNode root, int targetSum, List<Integer> path, int sum){
            // 当前结点为子结点 且 等于目标和
            if(root == null ){
                return;
            }

            path.add(root.val);
            if(root.left == null && root.right == null && sum + root.val == targetSum){
                result.add(new ArrayList<>(path));
            }
            dfs(root.left,targetSum, new ArrayList<>(path), sum + root.val);
            dfs(root.right,targetSum, new ArrayList<>(path), sum + root.val);
        }
    }


    /**
     * 优化空间复杂度
     * 将每次递归的对List的深拷贝 改成 双端队列的方式 ，每次回溯移除末尾的元素
     * */
    class Solution1 {
        List<List<Integer>> result = new ArrayList<>();
        Deque<Integer> deque = new ArrayDeque<>();
        public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
            dfs(root, targetSum);
            return result;
        }
        /**
         * 一个先序遍历的过程
         * 基线条件
         * 如果当前结点为null
         * */
        private void dfs(TreeNode root, int targetSum){
            // 当前结点为子结点 且 等于目标和
            if(root == null ){
                return;
            }

            deque.offerLast(root.val);
            targetSum -= root.val;
            if(root.left == null && root.right == null && targetSum == 0){
                result.add(new ArrayList<>(deque));
            }
            dfs(root.left,targetSum);
            dfs(root.right,targetSum);
            deque.pollLast();
        }
    }

}
